package com.shermanzhou.algorithm.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author zhouchaoqun
 * @date 2018/10/23 上午10:15
 */
public class BiTreeTraversal {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String strs = scanner.nextLine();
        List<String> data = new ArrayList<>(Arrays.asList(strs.split("\\s")));
        BiTree<String> stringBiTree = buildBiTree(data);
        postOrder(stringBiTree);
    }

    public static <E> BiTree<E> buildBiTree(List<E> data) {
        if (data == null || data.size() <= 0) {
            return null;
        }
        E e = data.remove(data.size() - 1);
        BiTree<E> left = buildBiTree(data);
        BiTree<E> right = buildBiTree(data);
        return new BiTree<>(left, right, e);
    }

    /**
     * 后序遍历
     * @param <E>
     * @return
     */
    public static <E> void postOrder(BiTree<E> root) {
        if (root == null) {
            return;
        }
        if (root.getLeft() != null) {
            postOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            postOrder(root.getRight());
        }
        System.out.println(root.getElement());
    }
}
class BiTree<E> {
    private BiTree<E> left;
    private BiTree<E> right;
    private E element;

    public BiTree<E> getLeft() {
        return left;
    }

    public void setLeft(BiTree<E> left) {
        this.left = left;
    }

    public BiTree<E> getRight() {
        return right;
    }

    public void setRight(BiTree<E> right) {
        this.right = right;
    }

    public E getElement() {
        return element;
    }

    public void setElement(E element) {
        this.element = element;
    }

    public BiTree(E element) {
        this.element = element;
    }

    public BiTree(BiTree left, BiTree right, E element) {
        this.left = left;
        this.right = right;
        this.element = element;
    }

    public BiTree() {
    }
}
